1. Field
The embodiments relate to processing operands, and in particular to a method, apparatus and system for processing large operands.
2. Description of the Related Art
The Karatsuba algorithm (A. Karatsuba and Y. Ofman, Multiplication of Multidigit Numbers on Automata, Soviet Physics-Doklady, 7 (1963), pages 595-596) was proposed in 1962 as an attempt to reduce the number of scalar multiplications required for computing the product of two large numbers. The classic algorithm accepts as input two polynomials of degree equal to 1, i.e., a(x)=a1x+a0 and b(x)=b1x+b0 and computes their product a(x)b(x)=a1b1x2+(a1b0+a0b1)x+a0b0 using three scalar multiplications. This technique is different from the naïve (also called the ‘schoolbook’) way of multiplying polynomials a(x) and b(x) which is to perform 4 scalar multiplications, i.e., find the products a0b0, a0b1, a1b0 and a1b1.
Karatsuba showed that you only need to do three scalar multiplications, i.e., you only need to find the products a1b1, (a1+a0)(b1+b0) and a0b0. The missing coefficient (a1b0+a0b1) can be computed as the difference (a1+a0)(b1+b0)−a0b0−a1b1 once scalar multiplications are performed. For operands of a larger size, the Karatsuba algorithm is applied recursively.
Karatsuba is not only applicable to polynomials but, also large numbers. Large numbers can be converted to polynomials by substituting any power of 2 with the variable x. One of the most important open problems associated with using Karatsuba is how to apply the algorithm to large numbers without having to lose processing time due to recursion. There are three reasons why recursion is not desirable. First, recursive Karatsuba processes interleave dependent additions with multiplications. As a result, recursive Karatsuba processes cannot take full advantage of any hardware-level parallelism supported by a processor architecture or chipset. Second, because of recursion, intermediate scalar terms produced by recursive Karatsuba need more than one processor word to be represented. Hence, a single scalar multiplication or addition requires more than one processor operation to be realized. Such overhead is significant. Third, recursive Karatsuba incurs the function call overhead.
Cetin Koc et. al. from Oregon Sate University (S. S. Erdem and C. K. Koc. “A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two”, Proceedings, 16th IEEE Symposium on Computer Arithmetic, J.-C. Bajard and M. Schulte, editors, pages 28-35, IEEE Computer Society Press, Santiago de Compostela, Spain, Jun. 15-18, 2003) describes a less recursive variant of Karatsuba where the size of the input operands needs to be a power of 2. This variant, however, still requires recursive invocations and only applies to operands of a particular size.